<?php
/**
 * @title 392. 判断子序列 - 预处理
 * @author start2004
 */

class Solution {

    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isSubsequence($s, $t) {
        /**
         * @since 2020-10-22 长度
         */
        $tlen = strlen($t);

        /**
         * @since 2020-10-22 26个字母位置
         */
        $chars = [];
        $code = ord("a");
        for($i=0; $i<26; $i++){
            $chars[chr($code+$i)] = -1;
        }
        // return $chars;

        /**
         * @since 2020-10-22 t每个字符后续第一个字符位置 数组
         */
        $nextChars = array_fill(0, $tlen, $chars);

        /**
         * @since 2020-10-22 迭代
         */
        for ($i=0; $i<$tlen; $i++){
            $char = $t[$i];

            /**
             * @since 2020-10-22 往前找字符, 找到自己或者字符串头, 停止
             */
            for($j=$i-1; $j>=0; $j--){
                $nextChars[$j][$char] = $i;
                if($char == $t[$j]){
                    break;
                } else {}
            }
        }
        // return $nextChars;


        /**
         * @since 2020-10-22 预处理完毕, 匹配s字符串
         */

        /**
         * @since 2020-10-22 长度
         */
        $slen = strlen($s);

        /**
         * @since 2020-10-22 迭代
         */
        for($i=0, $j=0; $i<$slen AND $j<$tlen; $i++){
            if($s[$i] == $t[$j]){
                $j++;
            } else {
                /**
                 * @since 2020-10-22 如果不相等, 字符串j下个字符s[i]出现位置
                 */
                $n = $nextChars[$j][$s[$i]];

                /**
                 * @since 2020-10-22 不存在下个字符s[i]
                 */
                if($n == -1){
                    return false;
                    break;
                } else {
                    /**
                     * @since 2020-10-22 存在下个字符, 位移+1
                     */
                    $j = $n+1;
                }
            }
        }

        /**
         * @since 2020-10-22 收官, j提前到字符串尾部, 结束循环, s字符串未匹配完整
         * @return
         */
        return $slen == $i;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.27_4.php
 */
$datas = [
    ["abc", "ahbgdc"],
    ["axc", "ahbgdc"],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->isSubsequence($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
